V predchádzajúcich dvoch častiach boli predstavené metódy triedenia dát optimalizované na rýchlosť. Treťou metódou je metóda vkladaním (vsúvaním), ktorej princíp je vysvetlený v tomto článku.
Predchádzajúce metódy (výberom a výmenou) utrieďovali nezotriedené pole dát naraz. Existuje však množstvo prípadoch, kde sa už do utriedeného poľa vkladá nový prvok.
Typickým prípadom sú napríklad rôzne športové podujatia, s ktorými súvisí zotrieďovanie výkonov na stavových tabuliach. Dáta sa na stavovej tabuli zotrieďujú priebežne.
Predstavme si súťaž v skoku do diaľky. Každý nový výkon sa v priebežnom poradí zapíše do tabuľky. Bolo by neefektívne po každom podanom výkone odznova zoradiť celú tabuľku podľa predchádzajúcich dvoch algoritmov. Preto pri zápise nového prvku do už usporiadaného poľa využívame metódu vkladaním.
Predpokladajme usporiadané n-prvkové pole
a[0] < a[1] < a[2] < a[3] ... a[n-3] < a[n-2] < a[n-1]
Do tohto poľa chceme vložiť nový prvok x.
1. krok Najskôr treba nový prvok porovnať so všetkými prvkami v poli, a nájsť pozíciu kam patrí. Všetky indexy poľa prebehneme pomocou cyklu for, pričom aktuálny prvok poľa porovnávame s novým prvkom. Ak platí nerovnosť a[k] >= x, potom prvok x patrí medzi prvky a[k-1] a a[k].
2. krok spočíva v presune všetkých prvkov a[k] až a[n-1] o jeden index "do prava" podľa schémy:
a[n] = a[n-1];
a[n-1] = a[n-2];
a[n-2] = a[n-3];
a[n-3] = a[n-4];
3. krok Medzera ktorá vznikne presunom v 2. kroku (a[k]) sa vyplní novým prvkom. Pre lepšie pochopenie algoritmu viď obrázok.
Triedenie prvkov vkladaním
Nasleduje zdrojový kód algoritmu v c++:
#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
int n;
int pole[10];
void vypis(int arr[]) {
for (int i=1;i<=arr[0];i++) {
cout << arr[i] << "\n";
}
}
int najdi_poziciu_pre(int prvok) {
int vratit;
// 1.krok - najst poziciu
for (int i=1;i<=pole[0];i++)
if (pole[i]>=prvok) {
vratit=i;
break;
}
if (vratit) return vratit;
else return pole[0];
}
void presun_vpravo(int index) {
// 2.krok - presun do prava od poziacie
// index. pole[index] sa uvolni
for (int i=pole[0]; i>=index; i--)
pole[i+1] = pole[i];
pole[0]++;
}
void vloz_na_poziciu(int poz1, int prv1) {
pole[poz1]=prv1;
}
void vloz(int prvok) {
int pozicia=najdi_poziciu_pre(prvok);
presun_vpravo(pozicia);
vloz_na_poziciu(pozicia, prvok);
}
void main() {
pole[0]=0;
vloz(5); // vlozi prvok do pola
vypis(pole); // "medzivypis"
vloz(4);
vypis(pole);
vloz(8);
vypis(pole);
vloz(9);
vypis(pole);
}
Komentár ku algoritmu:
Funkcia vloz() vkladá do poľa prvok, ktorý je uvedený ako argument tejto funkcie. Jednotlivé kroky algoritmu sú oddelené do samostatných funkcií :
1. krok ... najdi_poziciu_pre();
2. krok ... presun_vpravo();
3. krok ... vloz_na_poziciu();
Medzivypis poľa je realizovaný pomocou funkcie vypis().